//
// Created by LiuYou on 2021/12/2.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>


namespace Sort {


    static int randomNumberFromTheRange(int left, int right) {
        std::random_device randomDevice;
        std::default_random_engine randomEngine( randomDevice());
        std::uniform_int_distribution<> uniformIntDistribution( left, right );
        return uniformIntDistribution( randomEngine );
    }


    class QuickSort {
    public:
        static void quickSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }
            quickSort( arr, 0, arr.size() - 1 );
        }

        static void quickSort(std::vector<int>& arr, int left, int right) {
            if (left < right) {
                int randomIndex = randomNumberFromTheRange( left, right );
                std::swap( arr[randomIndex], arr[right] );

                const std::vector<int>& partitionRegionRangeIndex = partition( arr, left, right );

                quickSort( arr, left, partitionRegionRangeIndex[0] - 1 );
                quickSort( arr, partitionRegionRangeIndex[1] + 1, right );
            } else {
                return;
            }
        }

        static std::vector<int> partition(std::vector<int>& arr, int left, int right) {
            int leftSide = left - 1;
            int rightSide = right;
            int index = left;
            int pivot = arr[right];

            while (index < rightSide) {
                if (arr[index] < pivot) {
                    std::swap( arr[index++], arr[++leftSide] );
                } else if (arr[index] == pivot) {
                    ++index;
                } else {
                    std::swap( arr[index], arr[--rightSide] );
                }
            }

            std::swap( arr[index], arr[right] );
            return std::vector<int>{leftSide + 1, rightSide};
        }


    };


}


//using namespace Sort;


int main(int argc, char** argv) {
    std::vector<int> arr( 10 );
    for (int i = 0; i < 10; ++i) {
        arr[i] = Sort::randomNumberFromTheRange( 0, 100 );
    }

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;

    Sort::QuickSort::quickSort( arr );

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}

/*
todo 笔记: 点击CLion的 Recompile '*.cpp', 然后CLion会以 -g -std=gnu++14 -fsyntax-only 的 g++ 选项来编译源文件。
====================[ Compile | 6-QuickSort/QuickSort8.cpp | Debug ]============
Compiling '6-QuickSort/QuickSort8.cpp' ...
/usr/bin/c++ -g -std=gnu++14 -fsyntax-only /home/liuyou/CLionProjects/ZCYLS/6-QuickSort/QuickSort8.cpp

Compilation of '6-QuickSort/QuickSort8.cpp' finished
 */